In information processing systems, relatively slow storage devices (for example, auxiliary storage devices, such as Hard Disk Drives (HDD) and Solid State Drives (SSD)), are often used to store a large amount of data. If such a slow storage device is accessed each time an access request is issued, the data access becomes a bottleneck for performance. To deal with this, part of data stored in the slow storage device may be cached in a relatively fast memory (for example, a main storage device, such as a Random Access Memory (RAM)). The data cached in the memory may be supplied without access to the original storage device.
For example, there is considered a case of caching data that has a high possibility of being used, in a memory. In addition, for example, there is considered another case of keep holding used data in a memory, considering localization of access, which characterizes that data has a high possibility of being used again once the data is used. In this connection, in many cases, a memory used to cache data has less capacity than an original storage device, and therefore replacement of cached data occurs. As a method for selecting data to be removed from a memory, a Least Recently Used (LRU) algorithm or another page replacement algorithm is used. The LRU algorithm is to preferentially remove data that has been used the least recently (data that has not been used for the longest time).
By the way, data access includes data access with sequentiality, that is, sequential access to continuous areas on an original storage device and access to areas at fixed intervals. In the case where data access with sequentiality is detected, data to be requested next may be predicted and prefetched in a memory without waiting for further access requests. The prefetching achieves accelerated data access even to data that is not used repeatedly in a short time.
Note that there has been proposed a replacement determination circuit for determining a data block to be removed, from among a plurality of data blocks prefetched in a buffer. When having selected two or more candidate data blocks to be removed by the LRU algorithm, this proposed replacement determination circuit preferentially removes a data block that has not been accessed even once from the buffer, from among the selected candidates to be removed.
Further, there has been proposed a data processing apparatus having a cache control unit for prefetching data to be used by a processor, in a cache memory, independently of the processor. The cache control unit preferentially removes data used by the processor from among the data stored in the cache memory. Still further, there has been proposed a cache storage device that limits storage areas for prefetching among a plurality of storage areas. When prefetching new data, the proposed cache storage device removes data from a storage area used for prefetching, and does not remove any data from storage areas that are not used for prefetching.
Please see, for example, Japanese Laid-open Patent Publication Nos. 63-318654, 9-212421, and 2001-195304.
In many cases, data access with sequentiality is to request data over a wide area, and therefore data is prefetched in a memory one by one while the data access with sequentiality continues. In addition, in the data access with sequentiality, data in a plurality of areas in a storage device is requested only in one direction, and this direction does not change. For example, in the case of requesting data in a plurality of areas of a storage device in ascending order of addresses, there is a low possibility that the order is changed such that, after data in a certain area is requested, data in an area with a smaller address than the certain area is requested. As the data access with sequentiality progresses, part of data prefetched in a memory has a lower possibility of being used.
If a general page replacement algorithm is employed for all prefetched data and the other data, the other data that has a possibility of being used may be removed from a memory, earlier than prefetched data that has a low possibility of being used thereafter. This may reduce the use efficiency of the memory for caching, which is a problem. If storage areas for prefetching and the other storage areas are independently provided, as taught in Japanese Laid-open Patent Publication No. 2001-195304, such a situation may occur that one of these two kinds of areas has free space and the other is full, which may reduce the use efficiency of the memory for caching.